Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
- Declare a 2-dimensional array, arr, of n empty arrays. All arrays are zero indexed.
- Declare an integer, lastAnswer, and initialize it to 0.
- Declare an answers array.
- Parse through each query. The format of each query will be [type, x, y]. There are 2 types of queries, given as an array of strings for you to parse, treat them according to their type:
- Query:
1 x y- Let idx = ( (x ^ lastAnswer) % n ).
- Append the integer y to arr[idx].
- Query:
2 x y- Let idx = ( (x ^ lastAnswer) % n ).
- Assign the value arr[idx][y % size(arr[idx])] to lastAnswer.
- Store the new value of lastAnswer to answers array.
- Query:
- Return answers array.
Note: ^ is the bitwise XOR operation. % is the modulo operator.
Finally, size(arr[idx]) is the number of elements in arr[idx].
Function Description
Complete the dynamicArray function below.
dynamicArray has the following parameters:
- int n: the number of empty arrays to initialize in arr
- string queries[q]: query strings that contain 3 space-separated integers
Returns
- int[]: the results of each type 2 query in the order they are presented
Input Format
The first line contains two space-separated integers, n, the size of arr to create, and q, the number of queries, respectively.
Each of the q subsequent lines contains a query string, quires[i]
Constraints
- 1 <= n,q <= 10**5
- 0 <= x <= 10**9
- It is guaranteed that query type 2 will never query an empty array or index.
Sample Input
2 5
1 0 5
1 1 7
1 0 3
2 1 0
2 1 1
Sample Output
7
3
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Seq_ {
int *dat;
int sz;
} Seq;
Seq seq[100001];
void insert(int n, int y) {
seq[n].dat = realloc(seq[n].dat, seq[n].sz += 1);
seq[n].dat[seq[n].sz-1] = y;
}
int print(int n, int y) {
int t = seq[n].dat[y % seq[n].sz];
printf("%d\n", t);
return t;
}
int main() {
FILE *f = stdin;
int n, q;
fscanf(f, "%d %d", &n, &q);
int lastans = 0;
for (int i = 0; i < q; i++) {
int op, x, y;
fscanf(f, "%d %d %d", &op, &x, &y);
int seq = (x ^ lastans) % n;
if (op == 1)
insert(seq, y);
else // op == 2
lastans = print(seq, y);
}
return 0;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N = 0, Q = 0;
int lastans = 0;
int type, x, y;
int seq = 0;
int pos;
cin >> N >> Q;
vector < vector <int>> a(N);
for (int i = 0; i < Q; i ++) {
cin >> type >> x >> y;
seq = ((x ^ lastans) % N);
// cout << seq << endl;
if (type == 1) {
a[seq].push_back(y);
// cout << (seq) << " < -- " << y << endl;
}
else if (type == 2) {
pos = (y % a[seq].size());
//cout << "pos " << pos << endl;
lastans = a[seq][pos];
cout << lastans << endl;
}
}
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList < ArrayList());
}
int q = sc.nextInt();
int lastans = 0;
for (int i = 0; i < q; i++) {
if (sc.nextInt() == 1) {
lists.get((sc.nextInt() ^ lastans) % n).add(sc.nextInt());
}
else {
ArrayList < Integer> l = lists.get((sc.nextInt() ^ lastans) % n);
lastans = l.get(sc.nextInt() % l.size());
System.out.println(lastans);
}
}
}
}
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
class Solution
{
static void Main(string[] args)
{
List < int> seq;
var userInput = Console.ReadLine();
var userInputSplits = userInput.Split(' ');
var numberOfSequences = int.Parse(userInputSplits[0]);
var numberOfQueries = int.Parse(userInputSplits[1]);
var seqList = new List < List<int>>(new List < int>[numberOfSequences]);
var lastAns = 0;
for (var i = 0; i < numberOfQueries; i++)
{
userInput = Console.ReadLine();
userInputSplits = userInput.Split(' ');
var queryType = int.Parse(userInputSplits[0]);
var x = int.Parse(userInputSplits[1]);
var y = int.Parse(userInputSplits[2]);
var seqIndex = (x ^ lastAns) % numberOfSequences;
switch (queryType)
{
case 1:
if (seqList[seqIndex] != null)
seqList[seqIndex].Add(y);
else
{
seq = new List < int>();
seq.Add(y);
seqList[seqIndex] = seq;
}
break;
case 2:
seq = seqList[seqIndex];
lastAns = seq[y % seq.Count];
Console.WriteLine(lastAns);
break;
}
}
}
}
#4 Code Example with Javascript Programming
Code -
Javascript Programming
function processData(input) {
//Enter your code here
var lines = input.split('\n');
var NQ = lines[0].split(' ').map(Number);
var N = NQ[0];
var Q = NQ[1];
var lastans = 0;
var sequences = [];
for (var i = 0; i < = N; i++) {
sequences[i] = [];
}
lines.slice(1).forEach(function (line) {
var query = line.split(' ').map(Number);
var x = query[1];
var y = query[2];
if (query[0] === 1) {
var sequenceNum = (x ^ lastans) % N;
sequences[sequenceNum].push(y);
} else if (query[0] === 2) {
var sequenceNum = (x ^ lastans) % N;
var size = sequences[sequenceNum].length;
var element = sequences[sequenceNum][y % size];
console.log(element);
lastans = element;
}
});
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
#5 Code Example with Python Programming
Code -
Python Programming
a = input().split(' ')
N, Q = [int(e) for e in a]
arrays = [[] for _ in range(N)]
lastans = 0
def insert(x, y):
global lastans
arrays[(x ^ lastans) % N].append(y)
def printnum(x, y):
global lastans
inst = arrays[(x ^ lastans) % N]
lastans = inst[y % len(inst)]
print(lastans)
for i in range(Q):
line = [int(e) for e in input().split(' ')]
insert(line[1], line[2]) if line[0] == 1 else printnum(line[1], line[2])